Examples#
The following are some examples of the master theorem. Let’s look at them one by one.
Example 1#
This is the case of merge sort. Its time complexity is = + .
Solution
In this example, and are both equal to 2. So, = = 1 which means that = n = . That means case 2 is applied and = . Its final time complexity is = .
Example 2#
This is a case of binary search. Its time complexity is = + .
Solution
In this example, is equal to 1 and is equal to 2. So, = = 0 which means that = k = . That means case 2 is applied and = . Its final time complexity is = .
Example 3#
This is a case of binary tree traversal. Its time complexity is = 2 + .
Solution
In this example, is equal to 2 and is also equal to 2. So, = = 1 which means that = k = . That means case 1 is applied and = . Its final time complexity is = .
Example 4#
In this example, an algorithm has a time complexity of = 2 + .
Solution
In this example, is equal to 2 and is also equal to 2. So, = = 1 which means that = = . That means case 3 is applied and = . Its final time complexity is = .
Let’s test what we’ve learned so far with a quick assessment.
Quick Assessment
Question
What is the time complexity of = 4 + ?
In this example, is equal to 4 and is equal to 2. So, = = 2 which means that = = . That means case 2 is applied and = . Its final time complexity is = .
Example 5#
In this example, an algorithm has a time complexity of = + .
Solution
In this example, is equal to 1 and is equal to 2. So, = = 0 which means that = = . That means case 3 is applied. Its final time complexity is = .
Example 6#
In this example, an algorithm has a time complexity of = 16 + .
Solution
In this example, is equal to 16 and is equal to 4. So, = = 2 which means that = = . That means case 1 is applied. Its final time complexity is = .
Example 7#
In this example, an algorithm has a time complexity of = 2 + .
Solution
In this example, is equal to 2 and is equal to 2. So, = = 1 which means that = = . That means case 2 is applied. Its final time complexity is = = .
Example 8#
In this example, an algorithm has a time complexity of = 2 + .
Solution
In this example, is equal to 2 and is equal to 4. So, = = 0.5 which means that = = . That means case 2 is applied. Its final time complexity is = = .
Example 9#
In this example, an algorithm has a time complexity of = 3 + .
Solution
In this example, is equal to 3 and is also equal to 3. So, = = 1 which means that case 1 is applied. Its final time complexity is = .
Example 10#
In this example, an algorithm has a time complexity of = 3 + .
Solution
In this example, is equal to 3 and is equal to 4. So, which means that = = . By applying logarithmic rules we know that n > or > or > Case 3 is applied . Its final time complexity will be = .
Master Theorem
Quiz